package main

import (
	"fmt"
	"math"
)

/*
	：求数组小和

题目描述：
在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。
例子： [1,3,4,2,5]
1左边比1小的数：没有
3左边比3小的数：1
4左边比4小的数：1、3
2左边比2小的数：1
5左边比5小的数：1、3、4、 2
所以数组的小和为1+1+3+1+1+3+4+2=16

换个思路只要求出一个数右边有几个比他大然后加上对应数量的这个数就好了
*/
func main() {
	arr := []int{8, 3, 4, 10, 5, 10, 6}

	fmt.Println(arr)
	res := MergeSort1(arr)

	fmt.Println(arr, res)
}
func MergeSort1(arr1 []int) int {
	if arr1 == nil && len(arr1) < 2 {
		return 0
	}

	N := len(arr1)
	mergeSize := 1
	L := 0
	res := 0
	for true {
		L = 0
		for L < N {
			Mid := L + mergeSize - 1
			if Mid >= N {
				break
			}
			R := int(math.Min(float64(Mid+mergeSize), float64(N-1)))
			fmt.Println(L, Mid, R)
			res += Merge1(arr1, L, Mid, R)
			L = R + 1
		}
		if mergeSize > N/2 {
			break
		}
		mergeSize <<= 1
	}
	return res
}

func Merge1(arr []int, l, mid, r int) int {
	help := make([]int, r-l+1)

	p1 := l
	p2 := mid + 1
	i := 0
	res := 0
	for p1 <= mid && p2 <= r {

		if arr[p1] < arr[p2] {
			help[i] = arr[p1]
			res += arr[p1] * (r - p2 + 1) //核心代码
			//在左组小于右组的时候判断右组有几个数直接加上右组剩余的数量
			//p2>r的时候右组才没有数，p2=r的时候其实还有一个数在右组的所以要加+1最后返回累加的数就完事了
			p1++
			i++
		} else if arr[p2] < arr[p1] {
			help[i] = arr[p2]
			p2++
			i++

		} else {
			help[i] = arr[p1]
			p1++
			i++
		}
	}

	if p2 > r {

		for p1 <= mid {
			help[i] = arr[p1]
			p1++
			i++
		}
	}

	if p1 > mid {

		for p2 <= r {
			help[i] = arr[p2]
			p2++
			i++
		}
	}

	for i, v := range help {
		arr[l+i] = v

	}
	return res

}
